package kmp

func BuildNext(str string) []int {
    l := len(str)
    next := make([]int, l)
    i, prefix_len := 1, 0
    next[0] = 0
    for i < l {
        if str[i] == str[prefix_len] {
            // 如果当前字符与最长前后缀最后一个字符相等，则前后缀长度增加
            next[i] = prefix_len + 1
            i, prefix_len = i+1, prefix_len+1
        } else if prefix_len > 0 {
            // 如果当前字符与最长前后缀最后一个字符不相等，则找到前一个字符的前后缀，跳转过去重新匹配
            prefix_len = next[prefix_len-1]
        } else {
            // 如果当前字符前后缀在首位(一个都没匹配上)，则直接跳过当前字符，记为未匹配
            next[i] = 0
            i += 1
        }
    }
    return next
}

func KMP(str, patten string) int {
    next := BuildNext(patten)
    si, pi := 0, 0
    sl, pl := len(str), len(patten)
    for si < sl {
        if str[si] == patten[pi] {
            // 如果字符串和模板串匹配成功，则继续尝试匹配下一个字符
            si, pi = si+1, pi+1
        } else if pi > 0 {
            // 如果未匹配成功，并且当 pi 不在首位时(存在部分匹配上了)，则需要跳转回公共前后缀的位置，重新匹配
            pi = next[pi-1]
        } else {
            // 如果未匹配成功，并且 pi 已经在首位了(一个都没匹配上)，则需要跳过该字符，从下一个字符重新匹配
            si += 1
        }
        if pi == pl {
            // 当 匹配到了模板串的结尾时，则表示完全匹配，返回匹配的首位置
            return si - pl
        }
    }
    // 未匹配到，返回-1
    return -1
}
